public class Solution1653 {
    public int minimumDeletions(String s) {
        int len=s.length();
        int[] aDP=new int[len];
        int[] bDP=new int[len];
        if(s.charAt(0)=='a'){
            bDP[0]=1;
        }
        else{
            aDP[0]=1;
        }
        for (int i = 1; i < len; i++) {
            char tmpC=s.charAt(i);
            if(tmpC=='a'){
                aDP[i]=aDP[i-1];
                bDP[i]=bDP[i-1]+1;
            }
            else{
                aDP[i]=aDP[i-1]+1;
                bDP[i]=Math.min(aDP[i-1],bDP[i-1]);
            }
        }
        return Math.min(aDP[len-1],bDP[len-1]);
    }

    public static void main(String[] args) {
        Solution1653 s=new Solution1653();
        System.out.println(s.minimumDeletions("aababbab"));
    }
}
